package dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 343. 整数拆分
 */
public class P343 {

    public int integerBreak(int n) {
        int[] result = new int[1];
        bk(n, 0, new ArrayList<>(), result);
        return result[0];
    }

    public int dp(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            int max = dp[i - 1];
            for (int j = 1; j < i; j++) {
                max = Math.max(max, Math.max(dp[i - j], i - j) * j);
            }
            dp[i] = max;
        }
        return dp[n];
    }


    /**
     * @param n
     * @param now       当前已经使用的数量
     * @param savedList
     * @param result
     */
    private void bk(int n, int now, List<Integer> savedList, int[] result) {
        if (now == n) {
            int num = savedList.stream().reduce((a, b) -> a * b).get();
            if (num > result[0]) {
                result[0] = num;
            }
        } else {
            int end = 0;
            if (now == 0) {
                end = n - now - 1;
            } else {
                end = n - now;
            }
            for (int i = 1; i <= end; i++) {
                savedList.add(i);
                bk(n, now + i, savedList, result);
                savedList.remove(savedList.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int result = new P343().dp(2);
        System.out.println(result);
    }
}
